Having traced the mechanics of the insertion step, we now analyze how the structure of the inner shifting loop dictates Insertion Sort's overall performance. Its efficiency heavily depends on the initial state of the input array $A$.

  • Insertion Sort is characterized by its superior performance in specific scenarios, especially on nearly sorted data.
  • Best Case ($O(n)$): If the input array $A$ is already sorted, the inner shifting loop executes zero times. The algorithm performs only $n-1$ comparisons, resulting in linear time complexity.
  • Worst Case ($O(n^2)$): If the array is sorted in reverse order, every element must be compared against and shift all previously sorted elements, leading to a quadratic number of operations.
  • Due to its low constant factors, Insertion Sort is often preferred over Selection or Bubble Sort for small or nearly-sorted datasets.
  • It is an in-place sort, requiring only $O(1)$ extra space, and is stable, meaning it preserves the relative order of equal elements.
  • Complexity Summary:
    • Best Case: Time $O(n)$, Space $O(1)$
    • Average Case: Time $O(n^2)$, Space $O(1)$
    • Worst Case: Time $O(n^2)$, Space $O(1)$
Python Implementation: insertion_sort
1def insertion_sort(arr):
2    # Outer loop for unsorted part
3    for i in range(1, len(arr)):
4        key = arr[i]
5        j = i - 1
6
7        # Inner loop for shifting
8        while j >= 0 and key < arr[j]:
9            # This part is skipped in best case
10            arr[j + 1] = arr[j]
11            j -= 1
12        arr[j + 1] = key